% latex-chinese-template v0.3   http://ctex-kit.googlecode.com/
%
% See comments at the end of this file for more descriptions.

% Change winfonts to cjkfonts to use arphic fonts.
% Change winfonts to adobefonts to use Adobe fonts with xelatex.
% See http://tug.ctan.org/tex-archive/language/chinese/ctex/doc/
%  or http://ctex-kit.googlecode.com/svn/trunk/ctex/doc/
%  for details about options of ctex macro package.

\documentclass[adobefonts,UTF8,cs4size,a4paper,fancyhdr,fntef,hyperref]{ctexart}
\usepackage{amsmath}
\usepackage{listings}

\begin{document}

\title{SICP笔记}
\author{sudayly@gmail.com}

\maketitle
%\tableofcontents

\section{牛顿法求平方根}

给定一个正数x，其平方根$\sqrt x$的定义如下：
\[
	\sqrt x=y \text{\ }s.t. \text{\ } |y^2-x| \le \varepsilon \text{ and } y \ge 0 
\]

牛顿迭代法的基本思想是给定一个初值$y_0$，通过逼近$\sqrt x$直到误差小于某个阈值$\varepsilon$，比如说0.001。
其算法的基本步骤如下：
\begin{enumerate}
\item 给$y$设置初始值
\item 如$|y^2-x|\le0.001$，那么返回$y$，否则
\item 改进$y$的值，跳到第2步
\end{enumerate}


\section{递归与迭代}
本节给出求Fibnacci(n)的递归与迭代程序，并且讲述了把递归改成迭代的方法。
\begin{lstlisting}[language=Lisp]
(define (fib n)
	(cond ((= n 0) 0)
	      ((= n 1) 1)
	      (else (+ (fib (- n 1))
			    (- n 2)))))
\end{lstlisting}
\begin{lstlisting}[language=Lisp]
(define (fib n)
	(fib-iter 1 0 n))
(define (fib-iter a b count)
	(if (= count 0)
	    b
	    (fib-iter (+ a b) a (- count 1))))
\end{lstlisting}

在把递归程序改成迭代程序的时候，有以下两点需要注意：
\begin{enumerate}
\item 增加间接层，在这里就是(fib-iter a b count)
\item 增加本地变量，(a, b, count)，其中count是计数器，相当于C语言中的i，而a,b是求fib(n)中用到的变量
\end{enumerate}

\subsection{递归改成迭代遇到的一个错误}
在做Exercise 1.32遇到的错误，初始程序如下：
\begin{lstlisting}[language=Lisp]
(define (accumule combiner null-value term a next b)
    (define (iter a result)
        (if (> a b) null-value
            (iter (next a) (combiner result (term a)))))
    (iter a null-value))

(define (sum term a next b)
    (accumule + 0 term a next b))

(define (sum-cubes a b)
    (define (cube-term i) (* i i i))
    (define (cube-next i) (+ i 1))
    (sum cube-term a cube-next b))
\end{lstlisting}
迭代版本的accumule如下：
\begin{lstlisting}[language=Lisp]
(define (accumule combiner null-value term a next b)
    (if (> a b)
        null-value
        (combiner 
            (term a)
            (accumule combiner null-value term (next a) next b))))
\end{lstlisting}
在把递归的程序改成迭代后，sum-cubes计算结果始终为0，最终查出错误在于迭代版本程序处，
把(if (> a b) null-value改成(if (> a b) result即可，最后的迭代程序版本如下：
\begin{lstlisting}[language=Lisp]
(define (accumule combiner null-value term a next b)
    (define (iter a result)
        (if (> a b) result
            (iter (next a) (combiner result (term a)))))
    (iter a null-value))
\end{lstlisting}

原因分析：\\
尽管if (> a b)都起到了结束程序的作用，在在递归中起到的作用和在迭代中起到的作用是不同的，
在迭代中，如果if成立，则返回结果，
而在递归中，其返回的是(term (+ b 1))的结果。
换句话说，递归程序不需要我们自己累加值，而迭代需要。


\section{过程作为参数}
比如
\[
    \sum_{n=a}^b f(n) = f(a) + \cdots + f(b)
\]
可以抽象成
\begin{lstlisting}[language=Lisp]
(define (sum term a next b)
    (if (> a b)
        0
        (+ 
            (term a)
            (sum term (next a) next b))))
\end{lstlisting}
这样，$\sum_{i=a}^b i^3$可以定义如下：
\begin{lstlisting}[language=Lisp]
(define (sum-cubes a b)
    (sum cube a inc b))
(define (inc i) (+ i 1))
(define (cube x) (* x x x))
\end{lstlisting}


\end{document}

%%%%%%%%%%%%%%%%%%% END %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% How to compile:
%   install TeXLive 2009 as described below;
%   if you use adobefonts with xelatex, put Adobe fonts into ~/.fonts (Linux) or C:\WINDOWS\fonts (Windows);
%   else put sim*.ttf, sim*.ttc  into ~/.fonts and $TEXMFHOME/fonts/truetype/sim/ ;
%   See http://code.google.com/p/ctex-kit/wiki/SimpleChineseTemplates and Makefile for detailed building instructions.
%
%%%%%%%%%%%%%%%%%%% ENVIRONMENT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Tested with TeXLive 20090909 on Debian Squeeze: (use `tlmgr show xxx` for details)
%  xetex        r14602  3.1415926-2.2-0.9995.2
%  pdftex       r14549  3.1415926-1.40.10-2.2
%  ctex         r14619  0.93    (buggy, use r167 at http://ctex-kit.googlecode.com/)
%  zhmetrics    r14469          (buggy, use r167 at http://ctex-kit.googlecode.com/)
%  cjk          r15155  4.8.2
%  xecjk        r14567  2.3.5   (outdated, use r167 at http://ctex-kit.googlecode.com/)
%  arphic       r13822
%
% Way to install TeXLive 2009:
%  install-tl -repository http://ftp.ctex.org/mirrors/texlive/tlnet/  -profile texlive.profile
%
% Content of texlive.profile(without the leading "%" and white spaces):
%   # texlive.profile written on Fri Sep  4 07:00:20 2009 UTC
%   # It will NOT be updated and reflects only the
%   # installation profile at installation time.
%   selected_scheme scheme-basic
%   TEXDIR ~/texlive/2009
%   TEXDIRW ~/texlive/2009
%   TEXMFHOME ~/texmf
%   TEXMFLOCAL ~/texlive/texmf-local
%   TEXMFSYSCONFIG ~/texlive/2009/texmf-config
%   TEXMFSYSVAR ~/texlive/2009/texmf-var
%   binary_i386-linux 1
%   collection-basic 1
%   collection-fontsrecommended 1
%   collection-langcjk 1
%   collection-langlatin 1
%   collection-latex 1
%   collection-latexrecommended 1
%   collection-xetex 1
%   from_dvd 0
%   option_desktop_integration 1
%   option_doc 0
%   option_file_assocs 1
%   option_fmt 1
%   option_letter 0
%   option_path 0
%   option_post_code 1
%   option_src 0
%   option_sys_bin /usr/local/bin
%   option_sys_info /usr/local/info
%   option_sys_man /usr/local/man
%   option_w32_multi_user 1
%   option_write18_restricted 1

% View the generated pdf on Debian Squeeze(20090909) with:
%  xpdf (3.02-1.4+lenny1) + xpdf-chinese-simplified (20040727-1, depends cmap-adobe-gb1 (0+20051207-5))
%  evince (2.26.2-2) + poppler-data (0.2.1-5)
% !!! Remember installing poppler-data because it contains data about cmap-adobe-*.

%
% Hope these information useful for TeX newbies :-)
%   Liu Yubao <yubao.liu at gmail dot com>
%
% ChangeLog:
%   2009-09-11  Liu Yubao
%       * initial version, v0.1
%
%   2009-09-13  Liu Yubao
%       * use zhwinfonts to embed truetype fonts with pdflatex and dvipdfmx
%       * set hyperref properly for different encodings and TeX engines to avoid garbled bookmarks
%       % release v0.2
%
%   2010-06-20  Liu Haiyang
%       * simpify zhwinfonts and hyperref, v0.3
%

